package com.xw.class11;

import java.util.ArrayList;
import java.util.List;

/**
 * @author XW
 * @data 2023/8/17 10:19
 * @description N叉树如何通过二叉树来序列化、并完成反序列化
 */
public class Code03_NaryTreeToBinaryTree {
    // 提交时不要提交这个类
    public static class Node {
        public int val;
        public List<Node> children;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    };

    // 提交时不要提交这个类
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }

    class Codec{
        //N叉树序列化为二叉树
        public TreeNode encode(Node root){
            if(root == null ){
                return null;
            }
            TreeNode head = new TreeNode(root.val);
            head.left = en(root.children);
            return head;
        }

        private TreeNode en(List<Node> children) {
            TreeNode head = null;
            TreeNode cur = null;
            for(Node child : children){
                TreeNode treeNode = new TreeNode(child.val);
                if(head == null){
                    head = treeNode;
                }else{
                    cur.right = treeNode;
                }
                cur = treeNode;
                cur.left =en(child.children);
            }
            return head;
        }
        //二叉树序列化问N叉树
        public Node decode(TreeNode root){
            if(null == root){
                return null;
            }
            return new Node(root.val, de(root.left));
        }

        private List<Node> de(TreeNode root) {
            List<Node> children = new ArrayList<>();
            while(root != null){
                Node node = new Node(root.val, de(root.left));
                children.add(node);
                root = root.right;
            }
            return children;
        }
    }
}
